# 代码编写者： 李朔
# 开发时间： 2021/7/31 11:52
nums1=[4,5,6,0,0,0]
m=3
nums2=[1,2,3]
n=3

#方法1：暴力求解
# def insert_e(nums1,m,insert_position,e):
#     '''
#     :param nums1:要插入的数组
#     :param insert_position: 待插入位置
#     :param e: 待插入元素
#     :return: 当前m中存放的元素数量
#     '''
#     i=m
#     while i>insert_position:
#         nums1[i]=nums1[i-1]
#         i-=1
#     nums1[i]=e
#     print(nums1)
#     return m+1
# def merge(nums1,m,nums2,n):
#     nums1_pointer,nums2_pointer=0,0
#     while nums1_pointer<m and nums2_pointer<n:
#         if nums1[nums1_pointer]<=nums2[nums2_pointer]:
#             nums1_pointer+=1
#         else:
#             #找到了插入位置
#             m=insert_e(nums1,m,nums1_pointer,nums2[nums2_pointer])
#             nums2_pointer+=1
#     print('------------------------------------------------')
#     if nums1_pointer>=m:
#         while nums2_pointer<n:
#             nums1[nums1_pointer]=nums2[nums2_pointer]
#             nums1_pointer+=1
#             nums2_pointer+=1
#     return nums1

#方法2：引入额外空间
# def merge(nums1,m,nums2,n):
#     nums3 = []
#     nums1_p, nums2_p = 0, 0
#     while nums1_p < m and nums2_p < n:
#         if nums1[nums1_p] <= nums2[nums2_p]:
#             nums3.append(nums1[nums1_p])
#             nums1_p += 1
#         else:
#             nums3.append(nums2[nums2_p])
#             nums2_p += 1
#     while nums1_p < m:
#         nums3.append(nums1[nums1_p])
#         nums1_p += 1
#     while nums2_p < n:
#         nums3.append(nums2[nums2_p])
#         nums2_p += 1
#     nums1 = nums3
#     return nums1

#方法3从后面开始的指针遍历法
def merge(nums1,m,nums2,n):
    nums1_p,nums2_p=m-1,n-1
    i=m+n-1
    while nums2_p>=0 and nums1_p>=0:
        if nums1[nums1_p]<nums2[nums2_p]:
            #nums_2中的数比较大
            nums1[i]=nums2[nums2_p]
            nums2_p-=1
        else:
            nums1[i]=nums1[nums1_p]
            nums1_p-=1
        i-=1
    while nums2_p>=0:
        nums1[i]=nums2[nums2_p]
        nums2_p-=1
        i-=1
    return nums1
print(merge(nums1,m,nums2,n))
